package maxsumarrayafternegations1005

import "sort"

// nums中的数进行k次取反操作，
// 使得nums的和最大，返回最大值
// 例如，nums = [4,2,3], k = 1
// 取反后，nums = [4,-2,3]，和为5
// 注意：可以对同一个数进行多次取反操作
// 思路：首先对nums按照绝对值从大到小排序，然后正向遍历
// 1. 如果当前的数是负数，则k--，如果遍历过程中k为0，则结束循环
// 2. 如果遍历结束了k>0, 则取nums的最后一个值，按照k的奇偶性进行取反，基数取反，偶数不取反
// 3. 最后返回nums的和
func LargestSumAfterKNegationsMagnitude(nums []int, k int) int {
	// 1. 先对nums进行排序
	sort.Slice(nums, func(i, j int) bool {
		return abs(nums[i]) > abs(nums[j])
	})
	// 2. 然后逐次进行取反操作，如果当前的数是负数，则k--，
	for i := 0; i < len(nums); i++ {
		if nums[i] < 0 && k > 0 {
			nums[i] = -nums[i]
			k--
		}
	}
	// 3. 如果此时k为0，则结束循环；如果此时k大于0，则按照k的奇偶性进行取反
	if k > 0 {
		if k%2 == 1 {
			nums[len(nums)-1] = -nums[len(nums)-1]
		}
	}
	// 4. 最后返回nums的和
	sum := 0
	for _, num := range nums {
		sum += num
	}
	return sum
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
